Năm Thiên Phượng thứ 5 (18) 3 đời Vương Mãng, Phàn Sùng khởi binh ở huyện Cử, quận Thành Dương [2]2 , ban đầu có hơn trăm người, chuyển vào quận Thái Sơn, tự đặt hiệu cho mình là "Tam lão". Khi ấy 2 châu Thanh, Từ có nạn đói, giặc cướp nổi lên, thấy ông dũng mãnh, đều xin đi theo, trong thời gian 1 năm lên đến hơn vạn người. Các lực lượng nổi dậy của Bàng An 4, Từ Tuyên, Tạ Lộc, Dương Âm tập hợp vài vạn người, nối nhau quy phụ. Bọn họ cùng quay về tấn công huyện Cử, không hạ được, chuyển đến Cô Mạc [3] mà cướp bóc; nhân đó đánh bại tướng nhà Tân là Tham Thang hầu Điền Huống, giết vài vạn quan quân, bắc tiến Thanh Châu, đi đến đâu cướp bóc đến đấy. Nghĩa quân quay về Thái Sơn, đóng đồn ở Nam Thành [4]. Đến lúc này bọn Sùng mới tổ chức lại đội ngũ, đặt ra giao ước: giết người đền mạng, gây thương tích thì phải chịu thương tích tương tự; lấy lời nói để ước thúc, không có văn thư, cờ xí, bộ khúc, hiệu lệnh. Trong quân cao nhất là Tam lão, kế là Tòng sự, kế nữa là Tốt sứ, gọi nhau là Cự nhân.

Năm Địa Hoàng thứ 3 (22), tướng nhà Tân là Thái sư Vương Khuông, Canh thủy tướng quân Liêm Đan đưa hơn 10 vạn quân đến đánh, Phàn Sùng muốn chống lại, sợ nghĩa quân và quan quân lẫn vào nhau, nên lệnh cho mọi người nhuộm đỏ lông mày, do đó được gọi là quân Xích Mi 5. Nghĩa quân cả phá quan quân, giết hơn vạn người đuổi đến Vô Diêm [5], Đan chết trận, Khuông bỏ trốn. Sùng đưa hơn 10 vạn nghĩa quân quay về vây Cử vài tháng, nghe lời khuyên rằng đây là đất phát tích của ông, bèn giải vây mà đi. Bọn Sùng đánh quận Đông Hải (nhà Tân đổi là Nghi Bình), thất bại, bị giết vài ngàn người, bèn chuyển đi các quận Sở, Bái, Nhữ Nam, Dĩnh Xuyên, rồi về Trần Lưu, đánh hạ Lỗ Thành [6], chuyển đến Bộc Dương [7].